1. Field of the Invention
The present invention relates in general to computer-aided design (CAD) tools for designing integrated circuits (ICs), and in particular to a method for designing a clock tree for an IC.
2. Description of Related Art
Referring to FIG. 1, a clock tree 10 distributes a clock signal from its root 12 to a set of sinks 16 within an IC through a branching network of fan-out buffers 14A–14C. In the example of FIG. 1, clock tree 10 delivers a clock signal to only a small number of sinks 16 and requires only three levels of buffers 14A–14C to fan the clock signal out to all sinks, but a clock tree for a large IC may deliver a clock signal to a much larger number of sinks and can require many more levels of fan-out buffers.
After establishing positions of all fan-out buffers 14A–14C and routing signal paths between them and sinks 16, a clock tree synthesis (CTS) tool estimates the path delays from clock tree root 12 to all sinks 16 and then inserts additional buffers 18 into various branches of clock tree 10 as needed to reduce variations in path delays to the sinks, thereby to balance clock tree 10.
Since the range over which buffers 18 can affect path delays is limited, to improve the likelihood that the CTS tool will be able to adequately balance the clock tree by inserting buffers 18, the CTS tool tries to position each fan-out buffer 14A–14C to minimize variation in signal path distances from each fan-out buffer to the next lower level fan-out buffers or sinks 16 it drives. Two approaches (“bottom-up” and “top-down”) to determining where to position fan-out buffers 14 are commonly employed.
Bottom-Up Clock Tree Synthesis
FIG. 2 is a plan view of an IC layout showing positions of a set of sinks 16 within the layout. In a conventional, “bottom-up” approach to clock tree synthesis, the clock tree is synthesized by first assigning nearby sinks 16 to a set of clusters 20 such that each cluster has no more than the number of sinks that can be driven by a single fan-out buffer and such that each cluster spans as little area as possible. The CTS tool provides a separate first-level fan-out buffer 14A to drive the sinks 16 assigned to each cluster 20, with the fan-out buffer being suitably positioned near the centroid of the cluster.
As illustrated in FIG. 3, the CTS tool then assigns nearby first level buffers 14A to a set of clusters 22 and positions a second level buffer 14B near the centroid of each cluster 22 for driving the first level buffers 14A assigned to the cluster. The CTS tool then positions the top level buffer 14C near the centroid of all second level buffers 14B for driving the second level buffers.
FIG. 4 illustrates the layout of the resulting clock tree. FIG. 4 shows that the clusterization process employed by the bottom-up synthesis approach can usually provide relatively uniform path distances between the first level buffers 14A and sinks 16. However at higher levels of the clock tree, the path distances between buffers become less uniform, making it more difficult for a CTS tool to subsequently balance the clock tree through buffer insertions.
Top-Down Synthesis
Referring to FIG. 5, using a conventional, top-down partitioning approach to synthesizing a clock tree for delivering a clock signal to sinks 16, a CTS tool positions top level fan-out buffer 14C first, suitably near the centroid of all sinks 16. The CTS tool then divides the IC layout into a set of partitions 24–26, one for each second level buffer 14B, with each partition 24–26 being sized and shaped to contain approximately the same number of sinks 16. The CTS tool then positions a second level buffer 14B in each partition near the centroid of the sinks included in that partition.
As illustrated in FIG. 6, the CTS tool next divides each partition 24–26 into a set of smaller partitions 24A–24C, 25A–25C and 26A–26C, and positions each first level buffer 14A near the centroid of the sinks 16 contained within a corresponding one of partitions 24A–24C, 25A–25C and 26A–26C. The process ends at this point because each partition contains no more than the maximum number of sinks 16 that can be driven by a buffer.
FIG. 7 illustrates the layout of the resulting clock tree and shows that the top-down synthesis approach can usually provide relatively uniform path distance between buffers at the highest levels of the clock tree. However at lower levels of the clock tree, the path distances become less uniform, thereby making it more difficult for a CTS tool to balance the clock tree.